import com.sun.org.apache.regexp.internal.REUtil;

import java.util.*;

/**
 * @author yu
 * @date 2025年04月18日 17:53
 */
public class _20250405_01 {
    private static Map<Long, Long> dp = new HashMap<>(); // 静态变量共享状态
    private static long m;
    private static long w2, w3;

    public static long minCost(long n){
        if(n >= m) return 0;
        if(dp.containsKey(n)) return dp.get(n);

        long cost = Long.MAX_VALUE;
        // 乘2操作（严格防溢出）
        if (n <= Long.MAX_VALUE / 2) {
            long next2 = 2 * n;
            if (next2 <= m) {
                long subCost = minCost(next2) + w2; // 递归计算子问题
                cost = Math.min(cost, subCost);
            } else {
                cost = Math.min(cost, w2); // 直接达标
            }
        }

        // 乘3操作（严格防溢出）
        if (n <= Long.MAX_VALUE / 3) {
            long next3 = 3 * n;
            long subCost = (next3 >= m) ? w3 : (minCost(next3) + w3);
            cost = Math.min(cost, subCost);
        }
        /*if(n*2 <= m && n*2 <= Long.MAX_VALUE){
            long n2 = 2*n;
            cost = Math.min(cost, dp.getOrDefault(n2, Long.MAX_VALUE) + w2);
        }
        if(n*3 <= m && n*3 <= Long.MAX_VALUE){
            long n3 = 3*n;
            cost = Math.min(cost, dp.getOrDefault(n3, Long.MAX_VALUE) + w3);
        }*/

        dp.put(n,cost);
        return cost;
    }



    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        while (T-- > 0) {
            long n = scanner.nextLong();
            m = scanner.nextLong();
            w2 = scanner.nextLong();
            w3 = scanner.nextLong();
            dp = new HashMap<>(); // 每组测试前重置
            System.out.println(minCost(n));
        }
       /* for (int i = 0; i < T; i++) {
            long n = scanner.nextLong();
            long m = scanner.nextLong();
            long w2 = scanner.nextLong();
            long w3 = scanner.nextLong();
            System.out.println(minCost(n,m,w2,w3));
        }*/
    }

}


/*public static int minCost(int n, int m, int w2, int w3) {
    if (n >= m) return 0;

    // 使用HashMap替代大数组，避免内存问题
    HashMap<Integer, Integer> dp = new HashMap<>();

    // 初始化：所有i >= m的花费为0
    // 这里我们不需要初始化所有i>=m，只需要在需要时处理
    for (int i = m; i >= n; i--) {
        //所有i >= m的花费为0
        if (i >= m) {
            dp.put(i, 0);
            continue;
        }

        int cost = Integer.MAX_VALUE;

        // 检查2*i是否可能
        if (i <= m / 2) {
            int next2 = 2 * i;
            if (dp.containsKey(next2)) {
                cost = Math.min(cost, dp.get(next2) + w2);
            }
        }

        // 检查3*i是否可能
        if (i <= m / 3) {
            int next3 = 3 * i;
            if (dp.containsKey(next3)) {
                cost = Math.min(cost, dp.get(next3) + w3);
            }
        }

        if (cost != Integer.MAX_VALUE) {
            dp.put(i, cost);
        }
    }

    return dp.getOrDefault(n, -1);
}*/